package com.leetcode.www;

import java.util.ArrayList;
import java.util.List;

/**
 * Creared with IntelliJ IDEA.
 * Description:数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * User:yxd
 * Date:2022-03-13
 * Time:21:49
 */
public class DFS22 {
    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        back(list,new StringBuilder(),0,0,n);
        return list;
    }
    public void back(List<String> list,StringBuilder sb,int left,int right,int n){
        if (sb.length() == n * 2) {//此时括号数目达标可添加
            list.add(sb.toString());
            return;
        }
        if(left < n){//左括号的回溯
            sb.append("(");
            back(list,sb,left + 1,right,n);
            sb.deleteCharAt(sb.length() - 1);//回溯
        }
        if(right < left){//右括号的回溯 要保证每对括号都是有效的
            sb.append(")");
            back(list,sb,left,right + 1,n);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}
